import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 面试题 17.05. 字母与数字
 * https://leetcode-cn.com/problems/find-longest-subarray-lcci/
 */
public class Solutions_mianshi_17_05 {
    public static void main(String[] args) {
        String[] arr = {"A", "1", "B", "C", "D", "2", "3", "4", "E", "5", "F", "G",
                "6", "7", "H", "I", "J", "K", "L", "M"};
        // output: {"A", "1", "B", "C", "D", "2", "3", "4", "E", "5", "F", "G", "6", "7"}

        String[] result = findLongestSubarray(arr);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法二：前缀和优化版（11ms）
     */
    public static String[] findLongestSubarray(String[] array) {
        int len = array.length;
        // 记录正数、负数、0
        // preSum[5] = true：表示前缀和 5 出现过一次
        // 长度为 2 时，所表示的整数区间最多是 [-2, 2]
        int[] preSum = new int[len * 2 + 1];
        Arrays.fill(preSum, -2);
        // 关键：前缀和为 0 的位置，设置出现的索引为 -1
        preSum[len] = -1;
        int count = -1, left = -1;
        int sum = 0;

        for (int i = 0; i < len; i++) {
            char c = array[i].charAt(0);
            if (c >= '0' && c <= '9') {
                // 数字，减 1
                sum -= 1;
            } else {
                // 字母，加 1
                sum += 1;
            }
            if (preSum[sum + len] != -2) {
                // 存在，且前缀和 sum 的位置，出现在 last 索引中
                int last = preSum[sum + len];
                int curCount = i - last;
                // 若存在多个最长子数组，返回左端点最小的。所以要用大于，而不是大于等于
                if (curCount > count) {
                    // 记录下左侧的索引
                    left = last + 1;
                    // 最长子数组
                    count = curCount;
                }
            } else {
                // 不存在
                preSum[sum + len] = i;
            }
        }

        if (count == -1) {
            return new String[0];
        }
        String[] res = new String[count];
        System.arraycopy(array, left, res, 0, count);
        return res;
    }


    /**
     * 解法一：前缀和（26ms）
     */
    public static String[] findLongestSubarray2(String[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int count = -1;
        int sum = 0;
        map.put(0, -1);
        for (int i = 0; i < array.length; i++) {
            char c = array[i].charAt(0);
            if (c >= '0' && c <= '9') {
                // 数字
                sum -= 1;
            } else {
                // 字母
                sum += 1;
            }
            // 判断数字 -sum 是否出现过
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            } else {
                int last = map.get(sum);
                // 数量
                int cur = i - last;
                // 若存在多个最长子数组，返回左端点最小的。所以要用大于，而不是大于等于
                if (cur > count) {
                    left = last + 1;
                    count = cur;
                }
            }
        }

        if (count == -1) {
            return new String[0];
        }
        String[] res = new String[count];
        System.arraycopy(array, left, res, 0, count);
        return res;
    }
}
